home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / misc_lib / ln_sweep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  7.3 KB  |  206 lines
  1. /*******************************************************************************
  2. * Line plane sweep algorithm implementation - actual code.               *
  3. *                                           *
  4. * Written by:  Gershon Elber                              Ver 1.0, June 1993   *
  5. *******************************************************************************/
  6.  
  7. #include <stdio.h>
  8. #include <math.h>
  9. #include "irit_sm.h"
  10. #include "imalloc.h"
  11. #include "ln_sweep.h"
  12.  
  13. #define LS_XBBOX_OVERLAP(L1, L2) (L1 -> _MaxVals[0] > L2 -> _MinVals[0] && \
  14.                   L2 -> _MaxVals[0] > L1 -> _MinVals[0])
  15.  
  16. #if defined(ultrix) && defined(mips)
  17. static int LsSortCompare(VoidPtr Ptr1, VoidPtr Ptr2);
  18. #else
  19. static int LsSortCompare(const VoidPtr Ptr1, const VoidPtr Ptr2);
  20. #endif /* ultrix && mips (no const support) */
  21.  
  22. static void LsInitialize(LsLineSegStruct **Lines);
  23. static void LsIntersect(LsLineSegStruct *Lines);
  24. static int LsIntersectOne(LsLineSegStruct *L1, LsLineSegStruct *L2,
  25.               RealType *t1, RealType *t2);
  26.  
  27. /*******************************************************************************
  28. * Invokes the right functions in the right order...                   *
  29. *   The Lines segments are updated so the Inters slot holds the list of        *
  30. * intersections with the other segments, NULL if none.                   *
  31. *   Returned list might be in different order than that is given.           *
  32. *******************************************************************************/
  33. void LineSweep(LsLineSegStruct **Lines)
  34. {
  35.     if (Lines == NULL || *Lines == NULL)
  36.     return;
  37.  
  38.     LsInitialize(Lines);
  39.     LsIntersect(*Lines);
  40. }
  41.  
  42. /*******************************************************************************
  43. * Compare two LsLineSegStructs with according to _MinVals[1].               *
  44. *******************************************************************************/
  45. #if defined(ultrix) && defined(mips)
  46. static int LsSortCompare(VoidPtr Ptr1, VoidPtr Ptr2)
  47. #else
  48. static int LsSortCompare(const VoidPtr Ptr1, const VoidPtr Ptr2)
  49. #endif /* ultrix && mips (no const support) */
  50. {
  51.     RealType
  52.     Diff = ((*(LsLineSegStruct **) Ptr1)) -> _MinVals[1] -
  53.            ((*(LsLineSegStruct **) Ptr2)) -> _MinVals[1];
  54.  
  55.     return SIGN(Diff);
  56. }
  57.  
  58. /*******************************************************************************
  59. * Initialize the data structures for the plane sweep.                   *
  60. *******************************************************************************/
  61. static void LsInitialize(LsLineSegStruct **Lines)
  62. {
  63.     int i;
  64.     LsLineSegStruct *Line, **LineArray, **l;
  65.  
  66.     for (i = 0, Line = *Lines; Line != NULL; Line = Line -> Pnext, i++) {
  67.     RealType Size;
  68.  
  69.     Line -> _MinVals[0] = MIN(Line -> Pts[0][0], Line -> Pts[1][0]);
  70.     Line -> _MinVals[1] = MIN(Line -> Pts[0][1], Line -> Pts[1][1]);
  71.     Line -> _MaxVals[0] = MAX(Line -> Pts[0][0], Line -> Pts[1][0]);
  72.     Line -> _MaxVals[1] = MAX(Line -> Pts[0][1], Line -> Pts[1][1]);
  73.  
  74.     /* Computes the vector from first point to second. */
  75.     Line -> _Vec[0] = Line -> Pts[1][0] - Line -> Pts[0][0];
  76.     Line -> _Vec[1] = Line -> Pts[1][1] - Line -> Pts[0][1];
  77.  
  78.     /* Computes the line equation for the segment as Ax + By + C = 0,    */
  79.     /* sqrt(A^2 + B^2) = 1.                             */
  80.     Line -> _ABC[0] = Line -> _Vec[1];
  81.     Line -> _ABC[1] = -Line -> _Vec[0];
  82.     Size = sqrt(SQR(Line -> _ABC[0]) + SQR(Line -> _ABC[1]));
  83.     if (Size > 0.0) {
  84.         Line -> _ABC[0] /= Size;
  85.         Line -> _ABC[1] /= Size;
  86.         Line -> _ABC[2] = -(Line -> _ABC[0] * Line -> Pts[0][0] +
  87.                 Line -> _ABC[1] * Line -> Pts[0][1]);
  88.     }
  89.     else {
  90.         /* Zero length segment. Sets the line equation to never yield an */
  91.         /* intersection.                             */
  92.         Line -> _ABC[0] = Line -> _ABC[1] = 0.0;
  93.         Line -> _ABC[2] = 1.0;
  94.     }
  95.  
  96.     Line -> Inters = NULL;
  97.     }
  98.  
  99.     LineArray = (LsLineSegStruct **) IritMalloc(sizeof(LsLineSegStruct *) * i);
  100.     for (Line = *Lines, l = LineArray; Line != NULL; Line = Line -> Pnext)
  101.     *l++ = Line;
  102.     qsort(LineArray, i, sizeof(LsLineSegStruct *), LsSortCompare);
  103.     *Lines = *LineArray;
  104.     for (l = LineArray; --i; l++)
  105.     l[0] -> Pnext = l[1];
  106.     l[0] -> Pnext = NULL;
  107.     IritFree((VoidPtr) LineArray);
  108. }
  109.  
  110. /*******************************************************************************
  111. *   The actual intersections. Not a real plane sweep, but close...           *
  112. * March along the given list and intersect every line with all lines in the    *
  113. * domain that can affect it.                               *
  114. *******************************************************************************/
  115. static void LsIntersect(LsLineSegStruct *Lines)
  116. {
  117.     static int
  118.     IdNumber = 0;
  119.     LsLineSegStruct *Line, *Line2;
  120.  
  121.     for (Line = Lines; Line -> Pnext != NULL; Line = Line -> Pnext) {
  122.     RealType t, t2,
  123.         MaxY = Line -> _MaxVals[1];
  124.  
  125.     for (Line2 = Line -> Pnext; Line2 != NULL; Line2 = Line2 -> Pnext) {
  126.         if (Line2 -> _MinVals[1] > MaxY)
  127.         break; /* Cannot intersect any more */
  128.  
  129.         if (Line -> Id != Line2 -> Id &&
  130.         LS_XBBOX_OVERLAP(Line, Line2) &&
  131.         LsIntersectOne(Line, Line2, &t, &t2)) {
  132.         LsIntersectStruct
  133.             *Inter = (LsIntersectStruct *)
  134.             IritMalloc(sizeof(LsIntersectStruct)),
  135.             *Inter2 = (LsIntersectStruct *)
  136.             IritMalloc(sizeof(LsIntersectStruct));
  137.  
  138.         Inter -> t = t;
  139.         Inter -> OtherT = t2;
  140.         Inter -> OtherSeg = Line2;
  141.         Inter -> Id = IdNumber;
  142.         Inter -> Pnext = Line -> Inters;
  143.         Line -> Inters = Inter;
  144.  
  145.         Inter2 -> t = t2;
  146.         Inter2 -> OtherT = t;
  147.         Inter2 -> OtherSeg = Line;
  148.         Inter2 -> Id = IdNumber++;
  149.         Inter2 -> Pnext = Line2 -> Inters;
  150.         Line2 -> Inters = Inter2;
  151.         }
  152.     }
  153.     }
  154. }
  155.  
  156. /*******************************************************************************
  157. *   Computes a single intersection between two line segments.               *
  158. *   Returns TRUE if found an intersection and sets t1/t2 to the parameter      *
  159. * values of the intersection (t == 0 for first point, t == 1 for second).      *
  160. *******************************************************************************/
  161. static int LsIntersectOne(LsLineSegStruct *L1, LsLineSegStruct *L2,
  162.               RealType *t1, RealType *t2)
  163. {
  164.     RealType Dist11, Dist12, Dist21, Dist22, XDiff, YDiff, Det;
  165.  
  166.     Dist11 = L1 -> _ABC[0] * L2 -> Pts[0][0] +
  167.          L1 -> _ABC[1] * L2 -> Pts[0][1] +
  168.          L1 -> _ABC[2];
  169.     Dist12 = L1 -> _ABC[0] * L2 -> Pts[1][0] +
  170.          L1 -> _ABC[1] * L2 -> Pts[1][1] +
  171.          L1 -> _ABC[2];
  172.     if (Dist11 * Dist12 > 0.0) /* L2's two end points are on same size of L1. */
  173.     return FALSE;
  174.  
  175.     Dist21 = L2 -> _ABC[0] * L1 -> Pts[0][0] +
  176.          L2 -> _ABC[1] * L1 -> Pts[0][1] +
  177.          L2 -> _ABC[2];
  178.     Dist22 = L2 -> _ABC[0] * L1 -> Pts[1][0] +
  179.          L2 -> _ABC[1] * L1 -> Pts[1][1] +
  180.          L2 -> _ABC[2];
  181.     if (Dist21 * Dist22 > 0.0) /* L1's two end points are on same size of L2. */
  182.     return FALSE;
  183.  
  184.     /* Solve the following linear system for t1 and t2.                  */
  185.     /*                                          */
  186.     /* L1X1 + t1 L1Vx = L2X1 + t2 L2Vx                          */
  187.     /* L1Y1 + t1 L1Vy = L2Y1 + t2 L2Vy                          */
  188.     /*                                          */
  189.     /* or,                                      */
  190.     /*                                          */
  191.     /* t1 L1Vx - t2 L2Vx = L2X1 - L1X1                          */
  192.     /* t1 L1Vy - t2 L2Vy = L2Y1 - L1Y1                          */
  193.     /*                                          */
  194.     Det = L1 -> _Vec[1] * L2 -> _Vec[0] - L1 -> _Vec[0] * L2 -> _Vec[1];
  195.     if (Det == 0.0)
  196.     return FALSE;
  197.  
  198.     XDiff = L2 -> Pts[0][0] - L1 -> Pts[0][0];
  199.     YDiff = L2 -> Pts[0][1] - L1 -> Pts[0][1];
  200.  
  201.     *t1 = (YDiff * L2 -> _Vec[0] - XDiff * L2 -> _Vec[1]) / Det;
  202.     *t2 = (L1 -> _Vec[0] * YDiff - L1 -> _Vec[1] * XDiff) / Det;
  203.  
  204.     return *t1 > 0.0 && *t1 <= 1.0 && *t2 > 0.0 && *t2 <= 1.0;
  205. }
  206.